package com.googlecode.gaal.suffix.algorithm.impl;

import com.googlecode.gaal.data.api.IntSequence;
import com.googlecode.gaal.suffix.algorithm.api.LcpTableBuilder;

public class NaiveLcpTableBuilder implements LcpTableBuilder {

    /**
     * Naive algorithm for getting lcp array.
     * 
     * @param suffixTable
     *            the sorted suffix table
     * @param text
     *            the tokenized text with strings replaced by integers
     * @return the lcp array
     */
    @Override
    public int[] buildLcpTable(int[] suffixTable, IntSequence text) {
        int[] lcpTable = new int[suffixTable.length];
        lcpTable[0] = -1;
        for (int i = 1; i < suffixTable.length; i++) {
            lcpTable[i] = lcp(suffixTable[i], suffixTable[i - 1], text);
        }
        return lcpTable;
    }

    // Precondition: i and j are indices into text and i != j
    private static int lcp(int i, int j, IntSequence text) {
        int result = 0;

        // Eventually there will be a mismatch since sentinels are unique
        while (text.get(i++, -1) == text.get(j++, -2)) {
            result++;
        }
        return result;
    }
}
